//稀疏矩阵的链式存储结构：十字链表
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ElementType int

typedef struct OLNode
{
    int row;//1~m
    int col;//1~n
    ElementType value;
    struct OLNode *right, *down;//非零元素所在行，列后继链域
}OLNode, *OLink;

typedef struct CrossList
{
    OLink* row_head, *col_head;//行，列链表的头指针向量
    int m;//行数
    int n;//列数
    int len;//非零元素个数
}CrossList;

void CreatCrossList(CrossList* M, int m, int n, int len)
{
    M->m = m;
    M->n = n;
    M->len = len;
    if(!(M->row_head = (OLink*)malloc((m + 1) * sizeof(OLink))))
    {
        perror("row_head");
        exit(-1);
    }
    if(!(M->col_head = (OLink*)malloc((n + 1) * sizeof(OLink))))
    {
        perror("col_head");
        exit(-1);
    }
    memset(M->row_head, 0, (m + 1) * sizeof(OLink));
    memset(M->col_head, 0, (n + 1) * sizeof(OLink));//初始化为空链表

    int i = 0, j = 0, e = 0;//结点的行，列，值
    printf("请输入结点的行号,列号,值:\n");
    while(len)
    {
        scanf("%d %d %d", &i, &j, &e);
        if(i < 1||i > m||j < 1||j > n)
        {
            printf("行列号不合法,请重新输入:\n");
            continue;
        }

        int flag = 0;//检查位置是否重复
        for(OLNode* k = M->row_head[i]; k != NULL; k = k->right)
        {
            if(k->col == j)
            flag = 1;
        }
        if(flag)
        {
            printf("结点位置重复,请重新输入:\n");
            continue;
        }

        OLNode* p = (OLNode*)malloc(sizeof(OLNode));//申请结点
        if(p == NULL)
        {
            perror("Node application");
            exit(-1);
        }
        p->row = i; p->col = j; p->value = e;
        p->right = p->down = NULL;

        //行链表插入
        if(M->row_head[i] == NULL)//该行还没有结点
        {
            M->row_head[i] = p;
        }
        else if(p->col < M->row_head[i]->col)//新建结点列号<该行首结点列号
        {
            p->right = M->row_head[i];
            M->row_head[i] = p;
        }
        else//寻找插入位置
        {
            OLNode* q;
            for(q = M->row_head[i]; q->right && q->right->col < j; q = q->right);
            p->right = q->right;
            q->right = p;
        }

        //列链表插入
        if(M->col_head[j] == NULL)//该列还没有结点
        {
            M->col_head[j] = p;
        }
        else if(p->row < M->col_head[j]->row)//新建结点行号<改行首节点行号
        {
            p->down = M->col_head[j];
            M->col_head[j] = p;
        }
        else//寻找插入位置
        {
            OLNode* q;
            for(q = M->col_head[j]; q->down && q->down->row < i; q = q->down)
            p->down = q->down;
            p->down = p;
        }

        len--;
        printf("插入成功!\n");
        printf("请输入结点的行号,列号,值:\n");
    }

}

void PrintCrossList(CrossList* M)//打印十字链表
{
    for(int row = 0; row < M->m; row++)
    {
        OLNode* p = M->row_head[row];
        while(p != NULL)
        {
            printf("(%d, %d)=%d ", p->row, p->col, p->value);
            p = p->right;
        }
        printf("\n");
    }
}

int main()
{
    CrossList M;
    CreatCrossList(&M, 10, 10, 10);
    PrintCrossList(&M);
    return 0;
}